/**
* 求解约瑟夫环的问题
**/
#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
  int data;
  struct _node * next; // 指向下一个
} node;

/**
* 创建个数为n的循环链表
**/
node *create_data(int n)
{
  if (n < 1) { // 至少也要一个元素
    return NULL;
  }
  
  int i = 1;
  node *start,*p,*q;
  
  if ( NULL == ( start = (node*)malloc(sizeof(node)) ) ) {
    exit(-1);
  }
  start->data = i++;   // 头结点赋值
  
  p = start; // 游标,目前指向头指针
  while (i <= n) {
    if ( NULL == ( q = (node*)malloc(sizeof(node)) ) ) {
      exit(-1);
    }
    q->data = i++;
    
    p->next = q;
    p = q;
  }
  p->next = start; // 构成循环链表
  
  return start;
}

// 打印整个循环链表
void print_node(node *start)
{
  node *p = start;
  do {
    printf("%d,", p->data);
    p = p->next;
  }while (start != p);
  printf("\n");
}

// 我的答案
void josephus_my(int n,int k,int m)
{
  node * start = create_data(n); // 创建n个元素循环链表
  //print_node(start);
  
  int i;
  node *p = start, *q;
  
  while (--k) { p = p->next; } // 这里移动到k的前一个位置
  while (n--) { // 每次循环找到一个,循环完即可
    i = m;
    while (--i) { p = p->next; } // 循环到m的前一个
    
    q = p->next;
    p->next = q->next;
    printf("%d->", q->data);
    free(q);
  }
  printf("\n");
}

// pdf答案
void josephus_pdf(int n,int k,int m)
{
  node * start = create_data(n); // 创建n个元素循环链表
  //print_node(start);
  
  int i;
  node *p,*r,*list;
  
  p = start;
  while(k--) {
    r = p;
    p = p->next;
  }
  while(n--) {
    for (i=m-1;i--;r=p,p=p->next) {
    }
    r->next = p->next;
    printf("%d->", p->data);
    free(p);
    p = r->next;
  }
  printf("\n");
}

int main(int argc, char *argv[])
{
  int i,n=10,k=1,m=2;
  
  josephus_pdf(n,k,m);
  josephus_my(n,k,m);
  
  return 0;
}
